package com.shm.leetcode;

import java.util.*;

/**
 * 51. N 皇后
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：[["Q"]]
 *
 *
 * 提示：
 *
 * 1 <= n <= 9
 * 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
 *
 * @author SHM
 */
public class SolveNQueens {
    /**
     * 方法一：基于集合的回溯
     * 为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 \textit{columns}columns、\textit{diagonals}_1diagonals
     * 1
     * ​
     *   和 \textit{diagonals}_2diagonals
     * 2
     * ​
     *   分别记录每一列以及两个方向的每条斜线上是否有皇后。
     *
     * 列的表示法很直观，一共有 NN 列，每一列的下标范围从 00 到 N-1N−1，使用列的下标即可明确表示每一列。
     *
     * 如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。
     *
     * 方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)(0,0) 和 (3,3)(3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
     *
     *
     *
     * 方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
     *
     *
     *
     * 每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N!)O(N!)，其中 NN 是皇后数量。
     *
     * 空间复杂度：O(N)O(N)，其中 NN 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 NN，数组的长度为 NN，每个集合的元素个数都不会超过 NN。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens,-1);
        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagonals2 = new HashSet<>();
        backTrack(ans,queens,n,0,columns,diagonals1,diagonals2);
        return ans;
    }

    void backTrack(List<List<String>> ans,int[] queens,int n,int row,Set<Integer> columns,Set<Integer> diagonals1,Set<Integer> diagonals2){
        if(row==n){
            List<String> board = generateBoard(queens);
            ans.add(board);
        }else{
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)){
                    continue;
                }
                int diagonal1 = row-i;
                if (diagonals1.contains(diagonal1)){
                    continue;
                }
                int diagonal2= row+i;
                if (diagonals2.contains(diagonal2)){
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backTrack(ans,queens,n,row+1,columns,diagonals1,diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    List<String> generateBoard(int[] queens){
        int n = queens.length;
        List<String> board = new ArrayList<>();
        for (int i = 0; i <n; i++) {
            char[] c = new char[n];
            Arrays.fill(c,'.');
            c[queens[i]]='Q';
            board.add(new String(c));
        }
        return board;
    }
}
